package com.algorithm.cjm.csnote


/**
 * 双指针法
 *
 * 双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。
 *
 * Created by jieming.chen on 2021/2/2
 */

/**
 * 两数之和等于一个目标数字
 * 对数组应该 双指针方法
 */
fun twoSum(numbers: IntArray, target: Int): IntArray {
    var fromIndex = 0
    var endIndex = numbers.size - 1
    var index = 0
    while (index++ < numbers.size) {
        val sum = numbers[fromIndex] + numbers[endIndex]
        if (sum > target) {
            endIndex --
        } else if (sum == target) {
            return intArrayOf(fromIndex + 1, endIndex + 1)
        } else {
            fromIndex ++
        }
    }
    return intArrayOf()
}

/**
 * 对数字应用 双指针法
 */
fun judgeSquareSum(c: Int): Boolean {
    if (c == 0 || c == 1) {
        return true
    }
    var index = 0
    while (index * index <= c) {
        index++
    }

    Math.sqrt(c.toDouble())

    var i = 0
    var j = index
    while (i < j) {
        val sum = i * i + j * j
        if (sum == c) {
            return true
        } else if (sum > c) {
            j--
        } else {
            i--
        }
    }
    return false
}

/**
 * 反转
 * a、e、i、o、u
 * 对字符串应用双指针法
 */
fun reverseVowels(s: String): String {
    val toCharArray = s.toCharArray()
    val arrayOf = charArrayOf('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U')
    var i = 0
    var j = toCharArray.size - 1
    while (i < j) {
        if (arrayOf.contains(toCharArray[i]) && arrayOf.contains(toCharArray[j])) {
            val temp = toCharArray[i]
            toCharArray[i] = toCharArray[j]
            toCharArray[j] = temp
            i++
            j--
        } else if (!arrayOf.contains(toCharArray[i])) {
            i++
        } else {
            j--
        }
    }
    return String(toCharArray)
}

/**
 * 验证回文字符串
 */
fun validPalindrome(s: String): Boolean {
    return validPalindrome(s, false)
}

fun validPalindrome(s: String, hasRemove: Boolean): Boolean {
    var fromIndex = 0
    var endIndex = s.length - 1
    while (fromIndex < endIndex) {
        if (s[fromIndex] == s[endIndex]) {
            fromIndex ++
            endIndex --
        } else if (!hasRemove) {
            return validPalindrome(s.substring(fromIndex, endIndex), true) ||
                    validPalindrome(s.substring(fromIndex + 1, endIndex + 1), true)
        } else {
            return false
        }
    }
    return true
}

/**
 * 合并数组, 双指针法, 从前到后
 *  排序问题
 *  时间复杂度 O(n + m)
 */
fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int): Unit {
    val nums1_copy = IntArray(m)
    System.arraycopy(nums1, 0, nums1_copy, 0, m)

    var p1 = 0
    var p2 = 0

    var p = 0

    while (p1 < m && p2 < n)
        nums1[p++] = if (nums1_copy[p1] < nums2[p2]) nums1_copy[p1++] else nums2[p2++]

    if (p1 < m) {
        System.arraycopy(nums1_copy, p1, nums1, p1 + p2, m + n - p1 - p2);
    }
    if (p2 < n) {
        System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2);
    }
}

/**
 * 合并数组, 双指针法, 从后往前
 *  排序问题
 */
fun merge1(nums1: IntArray, m: Int, nums2: IntArray, n: Int): Unit {
    var index1 = m - 1
    var index2 = n - 1
    var indexMerge = m + n - 1
    while (index1 >= 0 || index2 >= 0) {
        if (index1 < 0) {
            nums1[indexMerge--] = nums2[index2--]
        } else if (index2 < 0) {
            nums1[indexMerge--] = nums1[index1--]
        } else if (nums1[index1] > nums2[index2]) {
            nums1[indexMerge--] = nums1[index1--]
        } else {
            nums1[indexMerge--] = nums2[index2--]
        }
    }
}

class ListNode(val value: Int) {
    var next: ListNode? = null
}

fun hasCycle(head: ListNode?): Boolean {
    var p1 = head?.next
    var p2 = head?.next?.next

    while (p1 != p2) {
        p1 = p1?.next
        p2 = p2?.next?.next
    }
    if (p1 == null || p2 == null) {
        return false
    }
    return true
}

fun findLongestWord(s: String, d: List<String>): String {
    val filter = d.filter { isMatch(s, it) }
    if (filter.size == 0) {
        return ""
    }
    val personComparator = Comparator<String> { o1, o2 ->
        if (o1.length > o2.length) {
            -1
        } else if (o1.length < o2.length) {
            1
        } else if(isZiDian(o1, o2)) {
            1
        } else {
            0
        }
    }
    val sortedWith = filter.sortedWith(personComparator)
    return sortedWith[0]
}

fun isZiDian(o1: String, o2: String): Boolean {
    var p1 = 0
    var p2 = 0
    while (p1 < o1.length && p2 < o2.length) {
        if (o2[p2] == o1[p1]) {
            p2++
            p1++
        } else {
            return o2[p2] > o1[p1]
        }
    }
    return true
}

private fun isMatch(s: String, target: String): Boolean {
    var p1 = 0
    var p2 = 0
    while (p1 < s.length && p2 < target.length) {
        if (s[p1] == target[p2]) {
            p1++
            p2++
        } else {
            p1++
        }
    }
    return p2 == target.length
}

fun main(args: Array<String>) {
//    println(twoSum(intArrayOf(2, 5, 7, 9), 9).contentToString())
//    println(judgeSquareSum(1231231))
//    println(reverseVowels("hello"))
//    println(validPalindrome("ececabbacec"))
//
//    val intArrayOf = intArrayOf(4, 5, 6, 0, 0, 0)
//    merge(intArrayOf, 3, intArrayOf(1, 2, 3), 3)
//    println(intArrayOf.contentToString())

//    println(hasCycle(null))
//
//    val node1 = ListNode(1)
//    val node2 = ListNode(2)
//    val node3 = ListNode(3)
//    node2.next = node3
//    node1.next = node2
//
//    println(hasCycle(node1))
//
//    node3.next = node1
//    println(hasCycle(node1))

//    println(findLongestWord("abpcplea", listOf("ale","apple","monkey","plea")))

    println(findLongestWord("abpcplea", listOf("a","b","c")))
}

